package leetcode;

public class Lc79 {

    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    visited[i][j] = true;
                    if (hasWord(board, i, j, word, 1))
                        return true;
                    visited[i][j] = false;
                }
            }
        }
        return false;
    }
    public boolean hasWord(char[][] board, int x, int y, String word, int idx) {
        if (idx == word.length())
            return true;
        visited[x][y] = true;
        if (x - 1 >= 0 && !visited[x - 1][y] && board[x - 1][y] == word.charAt(idx)) {
            if (hasWord(board, x - 1, y, word, idx + 1))
                return true;
            visited[x - 1][y] = false;
        }
        if (x + 1 < board.length && !visited[x + 1][y] && board[x + 1][y] == word.charAt(idx)) {
            if (hasWord(board, x + 1, y, word, idx + 1))
                return true;
            visited[x + 1][y] = false;
        }
        if (y - 1 >= 0 && !visited[x][y - 1] && board[x][y - 1] == word.charAt(idx)) {
            if (hasWord(board, x, y - 1, word, idx + 1))
                return true;
            visited[x][y - 1] = false;
        }
        if (y + 1 < board[0].length && !visited[x][y + 1] && board[x][y + 1] == word.charAt(idx)) {
            if (hasWord(board, x, y + 1, word, idx + 1))
                return true;
            visited[x][y + 1] = false;
        }
        visited[x][y] = false;
        return false;
    }
}
